#define _CRT_SECURE_NO_WARNINGS

#include"tanx.h"


void test_860()
{
	zr::Solution s;
	vector<int> bills = { 5,5,10,10,20 };
	cout << s.lemonadeChange(bills) << endl;

}

void test_2208()
{
	zr::Solution s;
	//vector<int> bills = { 5,19,8,1 };
	vector<int> bills = { 3,8,20 };
	cout << s.halveArray(bills) << endl;
}


void test_179()
{
	zr::Solution s;
	//vector<int> bills = { 3,30,34,5,9 };
	vector<int> bills = { 0,0,0 };
	cout << s.largestNumber(bills) << endl;
}

void test_376()
{
	zr::Solution s;
	//vector<int> bills = { 1,7,4,9,2,5 };
	//vector<int> bills = { 1,17,5,10,13,15,10,5,16,8 };
	vector<int> bills = { 1,2,3,4,5,6,7,8,9 };
	cout << s.wiggleMaxLength(bills) << endl;
}

void test_300_DP()
{
	zr::Solution s;
	//vector<int> bills = { 10,9,2,5,3,7,101,18 };
	//vector<int> bills = { 0,1,0,3,2,3 };
	vector<int> bills = { 7,7,7,7,7,7,7 };

	cout << s.lengthOfLIS_DP(bills) << endl;
}


void test_300_greedy()
{
	zr::Solution s;
	//vector<int> bills = { 10,9,2,5,3,7,101,18 };
	//vector<int> bills = { 0,1,0,3,2,3 };
	//vector<int> bills = { 7,7,7,7,7,7,7 };
	//vector<int> bills = { 10,9,2,5,3,4 };
	//vector<int> bills = { 4,10,4,3,8,9 };
	vector<int> bills = { 3,5,6,2,5,4,19,5,6,7,12 };

	cout << s.lengthOfLIS_greedy(bills) << endl;
}


void test_334()
{
	zr::Solution s;
	//vector<int> bills = { 1,2,3,4,5 };
	//vector<int> bills = { 5,4,3,2,1 };
	vector<int> bills = { 2,1,5,0,4,6 };

	cout << s.increasingTriplet(bills) << endl;
}

void test_674()
{
	zr::Solution s;
	//vector<int> bills = { 1,3,5,4,7 };
	//vector<int> bills = { 2,2,2,2,2 };
	vector<int> bills = { 2,1,3 };

	cout << s.findLengthOfLCIS(bills) << endl;
}

void test_121()
{
	zr::Solution s;
	//vector<int> bills = { 7,1,5,3,6,4 };
	vector<int> bills = { 7,6,4,3,1 };

	cout << s.maxProfit1(bills) << endl;
}

void test_122()
{
	zr::Solution s;
	//vector<int> bills = { 7,1,5,3,6,4 };
	//vector<int> bills = { 1,2,3,4,5 };
	vector<int> bills = { 7,6,4,3,1 };

	cout << s.maxProfit2(bills) << endl;
}

void test_1005()
{
	zr::Solution s;
	/*int k = 1;
	vector<int> bills = { 4,2,3 };*/
	/*int k = 3;
	vector<int> bills = { 3,-1,0,2 };*/
	/*int k = 2;
	vector<int> bills = { 2,-3,-1,5,-4 };*/
	/*int k = 3;
	vector<int> bills = { -2,5,0,2,-2 };*/
	/*int k = 8;
	vector<int> bills = { 8,-7,-3,-9,1,9,-6,-9,3 };*/
	int k = 2;
	vector<int> bills = { 5,6,9,-3,3 };
	cout << s.largestSumAfterKNegations(bills,k) << endl;
}

void test_2418()
{
	zr::Solution s;
	/*vector<string> names = { "Mary","John","Emma" };
	vector<int> heights = { 180,165,170 };*/
	vector<string> names = { "Alice","Bob","Bob" };
	vector<int> heights = { 155,185,150 };
	names = s.sortPeople(names, heights);
	cout << "[" ;
	for (const auto& e : names)
	{
		cout << "\"" << e << "\"";
	}
	cout << "]" << endl;
}

void test_870()
{
	zr::Solution s;
	/*vector<int> nums1 = { 2,7,11,15 };
	vector<int> nums2 = { 1,10,4,11 };*/
	vector<int> nums1 = { 12,24,8,32 };
	vector<int> nums2 = { 13,25,32,11 };

	nums1 = s.advantageCount(nums1,nums2) ;
	for (auto& e : nums1)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_409()
{
	zr::Solution s;
	//string str = "abccccdd";
	string str = "a";

	cout << s.longestPalindrome(str) << endl;
}

void test_942()
{
	zr::Solution s;
	//string str = "IDID";
	//string str = "III";
	string str = "DDI";

	vector<int> nums = s.diStringMatch(str);
	for (const auto& e : nums)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_455()
{
	zr::Solution ss;
	/*vector<int> g = { 1,2,3 };
	vector<int> s = { 1,1 };*/
	vector<int> g = { 1,2 };
	vector<int> s = { 1,2,3 };
	cout << ss.findContentChildren(g,s) << endl;
}

void test_553()
{
	zr::Solution s;
	//vector<int> bills = { 1000,100,10,2 };
	vector<int> bills = { 2,3,4 };

	cout << s.optimalDivision(bills) << endl;
}

void test_45()
{
	zr::Solution s;
	//vector<int> bills = { 2,3,1,1,4 };
	vector<int> bills = { 2,3,0,1,4 };

	cout << s.jump2(bills) << endl;
}

void test_45_dp()
{
	zr::Solution s;
	//vector<int> bills = { 2,3,1,1,4 };
	vector<int> bills = { 2,3,0,1,4 };

	cout << s.jump2_dp(bills) << endl;
}

void test_55()
{
	zr::Solution s;
	//vector<int> nums = { 2,3,1,1,4 };
	vector<int> nums = { 3,2,1,0,4 };

	cout << s.canJump(nums) << endl;
}

void test_134()
{
	zr::Solution s;
	/*vector<int> gas = { 1,2,3,4,5 };
	vector<int> cost = { 3,4,5,1,2 };*/
	/*vector<int> gas = { 2,3,4 };
	vector<int> cost = { 3,4,3 };*/
	/*vector<int> gas = { 4,5,3,1,4 };
	vector<int> cost = { 5,4,3,4,2 };*/
	/*vector<int> gas = { 2 };
	vector<int> cost = { 2 };*/
	/*vector<int> gas = { 1,2,3,4,3,2,4,1,5,3,2,4 };
	vector<int> cost = { 1,1,1,3,2,4,3,6,7,4,3,1 };*/
	vector<int> gas = { 5,1,2,3,4 };
	vector<int> cost = { 4,4,1,5,1 };

	/*vector<int> gas = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
	vector<int> cost = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };*/
	
	
	cout << s.canCompleteCircuit_DP(gas, cost) << endl;
	cout << s.canCompleteCircuit(gas, cost) << endl;

}

void test_738()
{
	zr::Solution s;
	//int n = 10;
	//int n = 1234;
	//int n = 332;
	int n = 963856657;

	cout << s.monotoneIncreasingDigits_bl(n) << endl;
	cout << s.monotoneIncreasingDigits(n) << endl;
}

void test_991()
{
	zr::Solution s;
	//int startValue = 2, target = 3;
	//int startValue = 5, target = 8;
	int startValue = 3, target = 10;

	cout << s.brokenCalc(startValue, target) << endl;
}

void test_56()
{
	zr::Solution s;
	//vector<vector<int>> intervals = { {1,3},{2,6},{8,10},{15,18} };
	//vector<vector<int>> intervals = { {1,4} ,{4,5} };
	vector<vector<int>> intervals = { {4,7} ,{1,4} };


	intervals = s.merge(intervals);
	for (const auto& e : intervals)
	{
		cout << "[" << e[0] << "," << e[1] << "]  ";
	}
	cout << endl;
}

void test_435()
{
	zr::Solution s;
	//vector<vector<int>> intervals = { {1,2} ,{2,3},{3,4},{1,3} };
	//vector<vector<int>> intervals = { {1,2} ,{1,2},{1,2} };
	vector<vector<int>> intervals = { {1,2} ,{2,3} };

	cout << s.eraseOverlapIntervals(intervals) << endl;
}

void test_452()
{
	zr::Solution s;
	//vector<vector<int>> intervals = { {10,16} ,{2,8},{1,6},{7,12} };
	//vector<vector<int>> intervals = { {1,2} ,{3,4},{5,6},{7,8} };
	vector<vector<int>> intervals = { {1,2} ,{2,3},{3,4},{4,5} };

	cout << s.findMinArrowShots(intervals) << endl;
}


int main()
{
	//test_860();

	//test_2208();

	//test_179();

	//test_376();

	//test_300_DP();

	//test_300_greedy();

	//test_334();

	//test_674();

	//test_121();

	//test_122();

	//test_1005();

	//test_2418();

	//test_870();

	//test_409();

	//test_942();

	//test_455();

	//test_553();

	//test_45();
	//test_45_dp();

	//test_55();

	//test_134();

	//test_738();

	//test_991();

	//test_56();

	//test_435();

	test_452();

	return 0;
}